package Leetcode.树;

/**
 * @Author: kirito
 * @Date: 2024/4/4 12:32
 * @Description:
 * 从叶结点开始的最小字符串
 * 给定一颗根结点为 root 的二叉树，树中的每一个结点都有一个 [0, 25] 范围内的值，分别代表字母 'a' 到 'z'。
 *
 * 返回 按字典序最小 的字符串，该字符串从这棵树的一个叶结点开始，到根结点结束。
 *
 * 注：字符串中任何较短的前缀在 字典序上 都是 较小 的：
 *
 * 例如，在字典序上 "ab" 比 "aba" 要小。叶结点是指没有子结点的结点。
 * 节点的叶节点是没有子节点的节点。
 *
 *
 *
 * 示例 1：
 *
 *
 *
 * 输入：root = [0,1,2,3,4,3,4]
 * 输出："dba"
 * 示例 2：
 *
 *
 *
 * 输入：root = [25,1,3,1,3,0,2]
 * 输出："adz"
 * 示例 3：
 *
 *
 *
 * 输入：root = [2,2,1,null,1,0,null,0]
 * 输出："abc"
 *
 *
 * 提示：
 *
 * 给定树的结点数在 [1, 8500] 范围内
 * 0 <= Node.val <= 25
 */

public class smallestFromLeaf {
    public static void main(String[] args) {
        String s1 = "aaa";
        String s2 = "acaaaaaaaaab";
        System.out.println(s1.compareTo(s2));

    }
    String ans = "~"; // 初始化答案字符串为 "~"，这是一个大于所有可能结果的字符串，用于比较获得最小字典序的字符串
    public String smallestFromLeaf(TreeNode root) {
        dfs(root, new StringBuilder()); // 调用深度优先搜索函数
        return ans; // 返回最终找到的最小字典序字符串
    }

    public void dfs(TreeNode node, StringBuilder sb) {
        if (node == null){
            return; // 如果节点为空，直接返回
        }
        sb.append((char)('a' + node.val)); // 将当前节点的值转换为对应的小写字母并添加到StringBuilder末尾

        if (node.left == null && node.right == null) { // 如果当前节点是叶子节点
            sb.reverse(); // 反转StringBuilder，因为我们是自底向上构建字符串的
            String S = sb.toString(); // 将StringBuilder转换为字符串
            sb.reverse(); // 再次反转StringBuilder，为了不影响其他路径的查询

            if (S.compareTo(ans) < 0){
                // 如果当前字符串的字典序小于已知的答案字符串
                ans = S; // 更新答案字符串
            }
        }
        dfs(node.left, sb); // 递归左子树
        dfs(node.right, sb); // 递归右子树
        sb.deleteCharAt(sb.length() - 1); // 回溯，删除StringBuilder末尾的字符，即当前节点的字符
    }

}
